/*
    XTU OJ: 1161
    by: fifth_light
*/

#include <stdio.h>

#define _N 100003
#define MOD(n) ((n) % _N)

int results[1005];

void init() {
    results[0] = 1;
    for (int i = 1; i < 1005; i++) {
        if (i % 2) {
            results[i] = 0;
        } else if (i == 2) {
            results[i] = 3;
        } else {
            results[i] = results[i - 2];
            for (int j = i - 2; j >= 0; j -= 2) {
                results[i] = MOD(results[i] + results[j] * 2);
            }
        }
    }
}

int main(void) {
    init();
    while (1) {
        int n;
        scanf("%d", &n);
        if (n == 0) {
            break;
        }
        printf("%d\n", results[n]);
    }
    return 0;
}
